package geekstudy.week1;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 *
 * 560. 和为K的子数组
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/
 *
 */
public class Week1SubarraySumEqualsK {

    public int subarraySum(int[] nums, int k) {

        int result = 0;
        for(int index = 0; index < nums.length; index++) {
            int subSum = nums[index];
            if(subSum == k ){
                result++;
            }
            //if(subSum > k) {
            //    break;
            //}
            for(int subIndex = index + 1; subIndex < nums.length; subIndex++) {
               subSum += nums[subIndex];
               if(subSum == k) {
                   result++;
                   //break;
               }
               //if(subSum > 1) {
               //    break;
               //}
            }
        }

        return result;
    }

    public int subarraySumByMap(int[] nums, int k) {
        int result = 0;

        // sum(i) = n[0] + n[1] + ... + n[i]
        // (sum(i) - k) + k = sum(i)
        // sum(i) -k  个数 和  k 个数相等
        Map<Integer, Integer> subSumMap = new LinkedHashMap<Integer, Integer>();
        subSumMap.put(0, 1);

        int subSum = 0;
        for(int index = 0; index < nums.length; index++) {
            subSum += nums[index];
            //if(subSum == k) {
            //    result += 1;
            //}

            // 还不明白 为什么result += 要放在前面
            result += subSumMap.getOrDefault(subSum - k, 0);

            if(!subSumMap.containsKey(subSum)) {
                subSumMap.put(subSum, 1);
            } else {
                subSumMap.put(subSum, subSumMap.get(subSum) + 1);
            }



        }


        return result;
    }

}
